package code;

public class Code213 {
	/*
	 * 枚举是否选择第一个房子，比较两者的，选择较大的值，确定是否选择1号房子，之后和以前的解法一样
	 */
    public int rob(int[] nums) {
        int ans=0;
        int n=nums.length;
        if(n==0)
        	return ans;
        if(n==1)
        	return nums[0];
        
        int[] dp=new int[n];
        /*
         * 选择1号房子
         */
        dp[0]=nums[0];
        dp[1]=nums[0];
        int i;
        /*
         * 因为选择了第一个房子，所以最后一个房子不能选
         */
        for(i=2;i<n-1;i++){
        	dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
        }
        ans=dp[n-2];
        /*
         * 不选择1号房子
         */
        dp[0]=0;
        dp[1]=nums[1];
        for(i=2;i<n;i++){
        	dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
        }
        ans=max(ans,dp[n-1]);
        
        return ans;
    }
    public int max(int a,int b){
    	return a>b?a:b;
    }
    public static void main(String[] args){
    	int[] nums={1,2,3,4};
    	System.out.println(new Code213().rob(nums));
    }
}
